#ifndef HASHMAP_H
#define HASHMAP_H

/**
 * \bibitem{teschner2003}
 * M. Teschner, B. Heidelberger, M. Müller, et al., ``Optimized spatial hashing for collision detection of deformable objects,'' in \textit{Vmv}, vol. 3, pp. 47--54, 2003.
 * 
 * Reference hash function Hash(x,y) = (73856093·x) XOR (19349663·y) mod N, where N is the length of hash table.
 */

#include "table.h"
#include "key.h"
#include "cell.h"
#include <unordered_map>
#include <omp.h>
#include <malloc.h>

namespace RealScan
{

// hash representation of `Table`
template <typename T, unsigned THREADS_NUM = 12>
class HashMap : public Table<T>
{
public:
    // Constructor
    HashMap() {}

    // Destructor
    ~HashMap() { std::unordered_map<Key, T>().swap(m_hashTable); malloc_trim(0); }

private:
    std::unordered_map<Key, T> m_hashTable;

public:
    ////// `Table` interface implementation //////
    // Search
    std::optional<T> search(const Key& key) const override
    {
        auto it = m_hashTable.find(key);
        if (it != m_hashTable.end())
        {
            return it->second;
        }
        return std::nullopt;
    }

    // Insert
    bool insert(const Key& key, const T& value) override
    {
        m_hashTable[key] = value;
        return true;
    }

    // Remove
    void remove(const Key& key) override
    {
        m_hashTable.erase(key);
    }

    // Vectorize
    void toVector(std::vector<Cell<T> >& vec, const Key& minKey, const Key& maxKey) const override
    {
        // Clear the vector
        vec.clear();

        #pragma omp parallel num_threads(THREADS_NUM)
        {
            std::vector<Cell<T> > localCells;

            // Parallel iteration over each row
            #pragma omp for nowait
            for (std::int32_t x = minKey.x; x <= maxKey.x; ++x)
            {
                for (std::int32_t y = minKey.y; y <= maxKey.y; ++y)
                {
                    auto it = m_hashTable.find({x, y});

                    if (it != m_hashTable.end())
                    {
                        localCells.push_back({{x, y}, it->second});
                    }
                }
            }

            // Merge local cells into the main vector
            #pragma omp critical
            {
                vec.insert(vec.end(), localCells.begin(), localCells.end());
            }
        }
    }

    // cells number
    std::size_t size() const override
    {
        return m_hashTable.size();
    }

    // memory used, const there
    std::size_t space() const override
    {
        // object size
        std::size_t total = sizeof(m_hashTable);

        // buckets size
        total += m_hashTable.bucket_count() * sizeof(void*);
        
        // all elements size
        for (std::size_t i = 0; i < m_hashTable.bucket_count(); ++i)
        {
            total += m_hashTable.bucket_size(i) * (sizeof(Key) + sizeof(T) + sizeof(void*));
        }

        return total;
    }
};

} /* RealScan */

#endif /* HASHMAP_H */